/*
 * @lc app=leetcode id=706 lang=cpp
 *
 * [706] Design HashMap
 */
#include <stdio.h>
#include <assert.h>

struct Node {
    Node(int key, int val):key(key), val(val), next(0) {}
    int key, val;
    Node *next;
};

class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        tsize_ = DefaultSize;
        table_ = new Node*[tsize_];
        for (int i=0; i<tsize_; i++) {
            table_[i] = NULL;
        }
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        int idx = getIdx(key);
        assert(idx >= 0 && idx < tsize_);

        Node* node = table_[idx];
        if (node) {

            if (node->key == key) {
                node->val = value;
                return;
            }

            while (node->next && node->next->key != key) {
                node = node->next;
            }

            if (!node->next) {
                node->next = new Node(key, value);
            } else {
                node->next->key = key;
                node->next->val = value;
            }
        } else {
            table_[idx] = new Node(key, value);
        }
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        int idx = getIdx(key);
        assert(idx >= 0 && idx < tsize_);

        Node* node = table_[idx];
        if (node) {
            while (node && node->key != key) {
                node = node->next;
            }

            if (node) {
                return node->val;
            }
        } 

        return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int idx = getIdx(key);
        assert(idx >= 0 && idx < tsize_);

        Node* node = table_[idx];
        if (node) {
            if (node->key == key) {
                table_[idx] = node->next;
                delete node;
            } else {
                while(node->next && node->next->key != key) {
                    node = node->next;
                }

                if (node->next && node->next->key == key) {
                    Node *toBeDelete = node->next;
                    node->next = node->next->next;
                    delete toBeDelete;
                }
            }
        }        
    }

private:

    int hash_(int key) {
        unsigned int hash = 5381;
        hash = (hash << 5) + hash + key;
        return hash;
    }

    int getIdx(int key) {
        int idx = hash_(key) % tsize_;
        return idx;
    }

    Node** table_;
    size_t tsize_;
    const static size_t DefaultSize = 256;
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

